package org.example;

public class Test3 {
    //leetcode 106 从中序和后续遍历序列构造二叉树
    int i;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        i = postorder.length - 1;
        return buildChidTree(inorder,postorder,0,inorder.length - 1);
    }

    public TreeNode buildChidTree(int[] inorder, int[] postorder, int left, int right) {
        if (left > right) return null;
        TreeNode root = new TreeNode(postorder[i]);
        int pivot = findIndex(inorder,postorder[i], left, right);
        i--;
        root.right = buildChidTree(inorder,postorder,pivot + 1,right);
        root.left = buildChidTree(inorder,postorder,left,pivot - 1);
        return root;

    }

    public int findIndex(int[] inorder, int target, int left, int right) {
        for (int i = left; i <= right; i++) {
            if (inorder[i] == target) return i;
        }
        return -1;
    }

    public static void main(String[] args) {
        Test3 test3 = new Test3();
        int[] arr1 = {9,3,15,20,7};
        int[] arr2 = {9,15,7,20,3};
        TreeNode ret = test3.buildTree(arr1,arr2);
        System.out.println(444);
    }
}
